import java.io.*;
import java.math.BigInteger;
import java.util.*;


class Read {
    StringTokenizer st=new StringTokenizer("");
    BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
    public String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public String nextLine() throws IOException {
        return bf.readLine();
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
}

public class Main {
    public static Read in=new Read();
    public static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main1(String[] args) throws IOException {
        char[] s=in.next().toCharArray();
        int n=s.length,num=0;
        for (int i = n - 2; i >= 0; i--) {
            if (s[i] != '-') {
                num = num * 10 + (s[i] - '0');
            }
        }
        int k=1,sum=0;
        while (num>0) {
            sum+=(num%10)*k;
            k+=1;
            num/=10;
        }
        sum%=11;
        if(sum==(s[n-1]-'0')||(sum==10&&s[n-1]=='X')) {
            System.out.println("Right");
        }else {
            if(sum!=10) {
                s[n-1]=(char) (sum+'0');
            }
            else {
                s[n-1]='X';
            }
            System.out.println(new String(s));
        }
    }
    public static void main2(String[] args) throws IOException {
        int n= in.nextInt(),m= in.nextInt();
        int n1= in.nextInt(),m1= in.nextInt();
        long[][] dp=new long[n+2][m+2];
        dp[0][1]=1;
        n1+=1;
        m1+=1;
        for (int i = 1; i <= n+1; i++) {
            for (int j = 1; j <= m+1; j++) {
                if(i!=n1&&j!=m1&&Math.abs(i-n1)+Math.abs(j-m1)==3||(i==n1&&j==m1)){
                    dp[i][j]=0;
                }
                else {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        out.println(dp[n+1][m+1]);
        out.close();
    }

    public static void main3(String[] args) throws IOException {
        int n=in.nextInt();
        int[][] nums=new int[n][4];
        for (int i = 0; i < n; i++) {
            nums[i][0]= in.nextInt();
            nums[i][1]= in.nextInt();
            nums[i][2]= in.nextInt();
            nums[i][3]= in.nextInt();
        }
        int x= in.nextInt(),y= in.nextInt();
        int ret=-1;
        for (int i = 0; i < n; i++) {

            if(x>=nums[i][0]&&x<=nums[i][0]+nums[i][2]&&y>=nums[i][1]&&y<=nums[i][1]+nums[i][3]) {
                ret=i+1;
            }
        }
        System.out.println(ret);
    }

    public static void main4(String[] args) throws IOException {
        int len= in.nextInt();
        int n= in.nextInt();
        int max=-1,min=-1;
        for (int i = 0; i < n; i++) {
            int x=in.nextInt();
            max=Math.max(Math.max(len-x+1,x),max);
            min=Math.max(Math.min(len-x+1,x),min);
        }
        out.println(min+" "+max);
        out.close();
    }

    public static void main5(String[] args) throws IOException {
        int n= in.nextInt();
        String[] nums=new String[n];
        for (int i = 0; i < n; i++) {
            nums[i]= in.next();
        }
        Arrays.sort(nums,(a,b)->{
            int i=0;
            while (i<Math.min(a.length(),b.length())&&a.charAt(i)==b.charAt(i)) {
                i++;
            }
            return i<Math.min(a.length(),b.length())?b.charAt(i)-a.charAt(i):0;
        });
        StringBuilder sb=new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(nums[i]);
        }
        System.out.println(sb);
    }
    public static void main6(String[] args) throws IOException {
        int n=in.nextInt();
        String[] s=new String[n];
        for (int i=0;i<n;i++) s[i]=in.next();
        for (int i=0;i<n;i++) {
            for (int j=i+1;j<n;j++) {
                String s1=s[i]+s[j];
                String s2=s[j]+s[i];
                if (Long.parseLong(s2)>Long.parseLong(s1)) {
                    String temp=s[i];
                    s[i]=s[j];
                    s[j]=temp;
                }
            }
        }
        for (int i=0;i<n;i++) System.out.print(s[i]);
    }
    static String[] s=new String[25];
    static int[] sum=new int[25];
    static int ret;
    static int ans,n;
    public static void main7(String[] args) throws IOException {
        n= in.nextInt();
        int max=Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            s[i]= in.next();
        }
        String a= in.next();
        for (int i = 0; i < n; i++) {
            if(s[i].substring(0,1).equals(a)) {
                sum[i]++;
                ans=s[i].length();
                dfs(i);
                sum[i]--;
                if(ret>max) max=ret;
            }
        }
        out.println(max);
        out.close();
    }

    private static void dfs(int x) {
        for (int i = 0; i < n; i++) {
           if(sum[i]<2&&find(x,i)>0) {
              ans+=find(x,i);
              sum[i]++;
              dfs(i);
              sum[i]--;
              ans-=find(x,i);
           }
        }
        if(ans>ret) ret=ans;
    }
    public static int  find(int index,int y) {
        for (int i = s[index].length()-1; i >= 0; i--) {
            if(s[index].substring(i,i+1).equals(s[y].substring(0,1))){
                int k=0;
                for (int j = i+1; j < s[index].length(); j++) {
                    k++;
                    if(!s[index].substring(j,j+1).equals(s[y].substring(k,k+1))) {
                        return 0;
                    }
                }
                return s[y].length()-k-1;
            }
        }
        return 0;
    }

    public static void main8(String[] args) throws IOException {
        String[] s=in.nextLine().split(" ");
        int[] nums=new int[s.length];
        for (int i = 0; i < nums.length; i++) {
            nums[i]=Integer.valueOf(s[i]);
        }
        int n=nums.length;
//        int[] f=new int[n];
        int count=0;
        int[] countA=new int[n];
        int[] ch=new int[n];
        int k=0;
        for (int i = 0; i < n; i++) {
            boolean flag=false;
            boolean c=false;
//            f[i]=1;
//            for (int j = 0; j < i; j++) {
//                if(nums[i]<=nums[j]) f[i]=Math.max(f[i],f[j]+1);
//            }
//            count=Math.max(count,f[i]);
            for (int j = 0; j < count; j++) {
                if(countA[j]<nums[i]) {
                    countA[j]=nums[i];
                    c=true;
                    break;
                }
            }

            if(!c) countA[count++]=nums[i];
            for (int j = 0; j < k; j++) {
                if(ch[j]>=nums[i]) {
                    flag=true;
                    ch[j]=nums[i];
                    break;
                }
            }
            if(!flag) {
                ch[k]=nums[i];
                k++;
            }
        }
//        PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->{
//            return a<=b?1:-1;
//        });
//        queue.offer(nums[0]);
//        for (int i = 1; i < n; i++) {
//            if(nums[i]<=queue.peek()) {
//                queue.poll();
//                queue.add(nums[i]);
//            }else {
//                queue.add(nums[i]);
//            }
//        }
        out.println(count);
        out.println(k);
        out.close();
    }

    public static void main9(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        Set<Integer> hash=new HashSet<>();
        int sever=0,repetition=0;
            while (in.hasNext()) {
                int num=in.nextInt();
                if(hash.contains(num)) {
                    repetition=num;
                }else {
                    hash.add(num);
                }
            }
        for (int i = 1; i < 100100; i++) {
             if(hash.contains(i+1)&&hash.contains(i-1)&&!hash.contains(i)){
                 sever=i;
             }
        }
        System.out.println(sever+" "+repetition);

    }
    static int m,x;

    public static void main10(String[] args) throws IOException {
        m=in.nextInt();
        x=in.nextInt();
        int[] num=new int[m];
        int[] a=new int[m];
        for (int i = 1; i <= m-1; i++) {
            num[i]=in.nextInt();
            a[i]=a[i-1]+num[i];
        }
        int l=1,r=m,ret=0;
        while (l<=r) {
            int mid=l+r>>1;
            if(check(mid,a)) {
                r=mid-1;
                ret=mid;
            }
            else l=mid+1;
        }
        System.out.println(ret);
    }
    public static boolean check(int y,int[] a) {
        for (int i=1;i+y<=m;i++) {
            if(a[i+y-1]-a[i-1]<2*x) return false;
        }
        return true;
    }

    public static void main11(String[] args) {
        System.out.println("2429042904288");
    }

    public static void main12(String[] args) throws IOException {
        int n=in.nextInt();
        long[] nums=new long[n+1];
        long[] sum=new long[n+1];
        for (int i = 1; i <= n; i++) {
            nums[i]=in.nextInt();
            sum[i]=sum[i-1]+nums[i];
        }
        long ret=0;
        for (int i = 1; i <= n-1; i++) {
            ret+=(sum[n]-sum[i])*nums[i];
        }
        out.println(ret);
        out.close();
    }

    public static int solution(int[] cards) {
        // Edit your code here
        int[] hash=new int[1010];
        int n=cards.length;
        for(int i=0;i<n;i++) {
            hash[cards[i]]++;
        }
        int ret=-1;
        for(int i=0;i<1010;i++) {
            if(hash[i]==1) {
                ret=i;
            }
        }
        return ret;
    }
}

class _Test2 {
    static int N = 100010;        //输入数组的最大长度
    static Node[] tr = new Node[N * 4];        //树 （节点数组）
    static int[] a = new int[N];        //存放输入数组

    public static void main1(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int f = 0;    //统计数组中1的个数
        for (int i = 1; i <= n; ++i) {
            a[i] = sc.nextInt();
            if (a[i] == 1) f++;
        }

        if (f != 0) {
            System.out.println(n-f);
            return;
        }

        build(1, 1, n);

        if (query(1, 1, n) != 1) {
            System.out.println(-1);
            return;
        }
        int ans = 0x3f3f3f3f;
        for (int i = 1; i <= n; ++i) {
            int l = i + 1, r = n + 1;
            while (l < r) {
                int mid = l + r >> 1;
                if (query(1, i, mid) == 1) r = mid;
                else l = mid + 1;
            }
            if (query(1, i, r) == 1) ans = Math.min(ans, r - i);
        }
        System.out.println(n-1+ans);
    }

    public static void main(String[] args) {

    }

    static int gcd(int a,int b){        //求最大公约数
        return b == 0 ? a:gcd(b,a%b);
    }

    static void pushup(int u) {
        tr[u].g = gcd(tr[u << 1].g, tr[u << 1 | 1].g);
    }

    static void build(int u, int l, int r) {    //建树
        if (l == r) tr[u] = new Node(l, r, a[r]);
        else {
            tr[u] = new Node(l, r, 0);
            int mid = l + r >> 1;
            build(u << 1, l, mid);
            build(u << 1 | 1, mid + 1, r);
            pushup(u);
        }
    }

    static int query(int u, int l, int r) {        //求区间gcd
        if (tr[u].l >= l && tr[u].r <= r) return tr[u].g;
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else return gcd(query(u << 1, l, r), query(u << 1 | 1, l, r));
    }

    static class Node {        //节点类
        int l, r, g;

        public Node(int l, int r, int g) {
            this.l = l;        //左子
            this.r = r;        //右子
            this.g = g;        //区间的最大公约数
        }
    }
    public int[] FindNumsAppearOnce (int[] nums) {
        int[] ret=new int[2];
        int k=0;
        Map<Integer,Integer> hash=new HashMap<>();
        for(int i=0;i<nums.length;i++) {
            hash.put(nums[i],hash.getOrDefault(nums[i],0)+1);
        }
        for(int i=0;i<nums.length;i++) {
            if(hash.get(nums[i])==1){
                ret[k++]=nums[i];
            }
        }
        if(ret[0]>ret[1]) {
            int a=ret[0];
            ret[0]=ret[1];
            ret[1]=a;
        }
        return ret;
    }

}